package leetcode.code0312;

/**
 * 动态规划 + 无辅助数组 <br>
 *
 * No.4
 *
 * @author CaoYu
 * @date 2021年10月3日
 * @description
 */
public class Solution3 extends Solution312 {

	@Override
	public int maxCoins(int[] nums) {
		int n = nums.length;
		int[][] dp = new int[n][n];
		for (int i = 0; i < n; i++) {
			dp[i][i] = this.lmr(nums, i - 1, i, i + 1);
		}
		for (int l = n - 1; l >= 0; l--) {// 结果在0上,i从大到小
			for (int r = l + 1; r < n; r++) {// 结果在n-1上, j从小到大
				int max = dp[l + 1][r] + this.lmr(nums, l - 1, l, r + 1);
				max = Math.max(max, dp[l][r - 1] + this.lmr(nums, l - 1, r, r + 1));
				for (int i = l + 1; i < r; i++) {
					max = Math.max(max, dp[l][i - 1] + dp[i + 1][r] + this.lmr(nums, l - 1, i, r + 1));
				}
				dp[l][r] = max;
			}
		}
		return dp[0][n - 1];// 结果在0上,i从大到小, 结果在n-1上, j从小到大
	}

	private int lmr(int[] nums, int l, int me, int r) {
		int lnum = l == -1 ? 1 : nums[l];
		int rnum = r == nums.length ? 1 : nums[r];
		return nums[me] * lnum * rnum;
	}

	/**
	 * 结果 = 没戳破*戳破*没戳破 <br>
	 * l到r范围内, 左右还没戳破, 戳破l到r气球, 能获得的最大值
	 *
	 * @param nums
	 * @param l
	 * @param r
	 * @param dp
	 * @return
	 */
	public int f(int[] nums, int l, int r, Integer[][] dp) {
		if (dp[l][r] != null)
			return dp[l][r];
		if (l == r) {
			dp[l][r] = nums[l - 1] * nums[l] * nums[l + 1];
			return dp[l][r];
		}
		int max = f(nums, l + 1, r, dp) + nums[l] * nums[l - 1] * nums[r + 1];
		max = Math.max(max, f(nums, l, r - 1, dp) + nums[r] * nums[l - 1] * nums[r + 1]);
		for (int i = l + 1; i < r; i++) {
			max = Math.max(max, f(nums, l, i - 1, dp) + f(nums, i + 1, r, dp) + nums[i] * nums[l - 1] * nums[r + 1]);
		}
		dp[l][r] = max;
		return max;
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
